//
//  LongestIncreasingPath.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/26.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  329. 矩阵中的最长递增路径

import UIKit

/*
 329. 矩阵中的最长递增路径

 给定一个整数矩阵，找出最长递增路径的长度。

 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

 示例 1:

 输入: nums =
 [
   [9,9,4],
   [6,6,8],
   [2,1,1]
 ]
 输出: 4
 解释: 最长递增路径为 [1, 2, 6, 9]。
 示例 2:

 输入: nums =
 [
   [3,4,5],
   [3,2,6],
   [2,2,1]
 ]
 输出: 4
 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
 */

class LongestIncreasingPath: NSObject {
    
    var longestPath = 0
    var memo:[[Int]] = []
    
    /*回溯算法过于耗时，该题用回溯算法会超出时间限制，不能提交通过.*/
    func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
        guard matrix.count > 0 else {
            return 0
        }
        
        //根据题意，要求最长递增路径。那么起点必然满足上下左右四个点要么是空，要么大于等于这个点，所以可以先把可能的起点的找出来
        
        let m = matrix.count
        let n = matrix[0].count
        
        var startPoint:[[Int]] = []
        
        for i in 0 ..< m {
            for j in 0 ..< n{
                if self.isVailedStartPoint([i,j], matrix) == true{
                    startPoint.append([i,j])
                }
            }
        }
        print("可用的起点有\(startPoint)")
        
        //找到所有起点进行回溯算法

        let flagArr = [[Bool]](repeating: [Bool](repeating: false, count: n), count: m)
        
        memo = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        
        for i in 0 ..< m{
            for j in 0 ..< n{
                longestPath = max(longestPath, self.memoryDFS([i,j], matrix))
            }
        }
        
//        for start in startPoint{
//            self.dfs(start, [], matrix, flagArr)
//        }
        
        return longestPath
    }
    
    //深度搜索算法+记忆化    可以很大程度上提升效率
    /*
     以测试用例
     [9,9,4],
     [6,6,8],
     [2,1,1]
     
     像动态规划一样，构建同样的矩阵memo
     [0,0,0],
     [0,0,0],
     [0,0,0]
     
     每个点的数字代表以这个点为起点的最长递增路径的路径长度。
     根据题意我们可以得出 每个点的值 等于其上下左右所有大于它本身的数的最大值 再加上1
     假设某点上下左右都大于原值，则有
     f(i,j) = max{f(i-1,j), f(i+1,j), f(i,j-1), f(i,j+1)} + 1
     
     以以上用例的0,0坐标为例。
     9上面越界，左边越界，下面6小于本身，右边9小于本身，那么memo(0,0) 只能等于1
     
     坐标(0,1)也是同样的方式推算。可知 memo(0,1) = 1
     
     坐标(0,2)，我们发现左边9大于自身的值，满足条件，且上下左右仅有这一个方向满足条件。因此 f(0,1) = max(f(0,1)) + 1
     这里刚好memo(0,1)刚刚计算过，可以直接相加。
     最终得出 memo(0,2) = 2。这个结果也要缓存在memo里面，下次再有其他节点访问到这里就可以不用计算直接返回，大大提升算法效率
     
     第一行就都算出来了，我们用同样的方式算出memo中的每个元素。最后就可以找到题目所求的最长路径
     最终的memo结果为:
     [1,1,2],
     [2,2,1],
     [3,4,2]
     
     */
    func memoryDFS(_ enterPoint:[Int], _ sourceArr:[[Int]]) -> Int{
        let row = enterPoint[0]
        let column = enterPoint[1]
        if memo[row][column] != 0 {
            return memo[row][column]
        }
        memo[row][column] += 1

        let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
        let nextPointLeft = [enterPoint[0], enterPoint[1] - 1]
        let nextPointDown = [enterPoint[0] + 1, enterPoint[1]]
        let nextPointRight = [enterPoint[0], enterPoint[1] + 1]
        
        if self.isInSideAndBigger(enterPoint, nextPointUp, sourceArr) == true {
            memo[row][column] = max(memo[row][column], 1 + self.memoryDFS(nextPointUp, sourceArr))
        }
        
        if self.isInSideAndBigger(enterPoint, nextPointLeft, sourceArr) == true {
            memo[row][column] = max(memo[row][column], 1 + self.memoryDFS(nextPointLeft, sourceArr))
        }
    
        if self.isInSideAndBigger(enterPoint, nextPointDown, sourceArr) == true {
            memo[row][column] = max(memo[row][column], 1 + self.memoryDFS(nextPointDown, sourceArr))
        }
     
        if self.isInSideAndBigger(enterPoint, nextPointRight, sourceArr) == true {
            memo[row][column] = max(memo[row][column], 1 + self.memoryDFS(nextPointRight, sourceArr))
        }
        return memo[row][column]
    }
    
    //判断目标值是否在界内并且大于原来的值
    func isInSideAndBigger(_ currentPoint:[Int], _ targetPoint:[Int] , _ matrix: [[Int]]) -> Bool{
        let m = matrix.count-1
        let n = matrix[0].count-1
        if targetPoint[0] < 0 || targetPoint[0] > m ||
           targetPoint[1] < 0 || targetPoint[1] > n{
            return false
        }
        
        if matrix[currentPoint[0]][currentPoint[1]] >= matrix[targetPoint[0]][targetPoint[1]] {
            return false
        }else{
            return true
        }
    }
    
    
    
    
    
    
    
    
    
    
    /*
     [3,4,5],
     [3,2,6],
     [2,2,1]
     */
    func dfs(_ enterPoint:[Int], _ tmpArr:[[Int]], _ sourceArr:[[Int]], _ flagArr:[[Bool]]){
        if self.isOutSide(enterPoint, sourceArr) == true {
            return
        }
        
        var arr = tmpArr
  
        
        var flagArr = flagArr
        if arr.count == 0 {
            arr.append(enterPoint)
            longestPath = max(longestPath, arr.count)
            flagArr[enterPoint[0]][enterPoint[1]] = true
            let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
            let nextPointLeft = [enterPoint[0], enterPoint[1] - 1]
            let nextPointDown = [enterPoint[0] + 1, enterPoint[1]]
            let nextPointRight = [enterPoint[0], enterPoint[1] + 1]
            
            self.dfs(nextPointUp, arr, sourceArr, flagArr)
            self.dfs(nextPointLeft, arr, sourceArr, flagArr)
            self.dfs(nextPointDown, arr, sourceArr, flagArr)
            self.dfs(nextPointRight, arr, sourceArr, flagArr)
            
        }else{
            
            let exPoint = arr.last!
            //判断是否到了边界 条件是上下左右是空或者都是小于自己的数
              if self.isEndPoint(enterPoint, sourceArr, flagArr) == true {
                if sourceArr[exPoint[0]][exPoint[1]] == sourceArr[enterPoint[0]][enterPoint[1]] {
                }else{
                    arr.append(enterPoint)
                }
                longestPath = max(longestPath, arr.count)
                return
              }
            
            //let exPoint = arr.last!
            if sourceArr[exPoint[0]][exPoint[1]] >= sourceArr[enterPoint[0]][enterPoint[1]] {
                return
            }else{
                arr.append(enterPoint)
                flagArr[enterPoint[0]][enterPoint[1]] = true
                let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
                let nextPointLeft = [enterPoint[0], enterPoint[1] - 1]
                let nextPointDown = [enterPoint[0] + 1, enterPoint[1]]
                let nextPointRight = [enterPoint[0], enterPoint[1] + 1]
                
                self.dfs(nextPointUp, arr, sourceArr, flagArr)
                self.dfs(nextPointLeft, arr, sourceArr, flagArr)
                self.dfs(nextPointDown, arr, sourceArr, flagArr)
                self.dfs(nextPointRight, arr, sourceArr, flagArr)
            }
        }
    }
    
    /*
     [9,9,4],
     [6,6,8],
     [2,1,1]
     */
    
    func isVailedStartPoint(_ enterPoint:[Int], _ matrix: [[Int]]) -> Bool{
        //起点必然满足上下左右四个点为空或大于等于这个点

        //上
        let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
        let isOutUp = self.isOutSide(nextPointUp, matrix)
        
        if isOutUp {
            //越界
        }else{
            //没有越界
            if matrix[nextPointUp[0]][nextPointUp[1]] < matrix[enterPoint[0]][enterPoint[1]] {
                //且这个值小于原值 可直接返回false
                return false
            }
        }

        
        //左
        let nextPointLeft = [enterPoint[0], enterPoint[1] - 1]
        let isOutLeft = self.isOutSide(nextPointLeft, matrix)
        
        if isOutLeft {
            //越界
        }else{
            //没有越界
            if matrix[nextPointLeft[0]][nextPointLeft[1]] < matrix[enterPoint[0]][enterPoint[1]] {
                //且这个值小于原值 可直接返回false
                return false
            }
        }
        
        //下
        let nextPointDown = [enterPoint[0] + 1, enterPoint[1]]
        let isOutDown = self.isOutSide(nextPointDown, matrix)
        
        if isOutDown {
            //越界
        }else{
            //没有越界
            if matrix[nextPointDown[0]][nextPointDown[1]] < matrix[enterPoint[0]][enterPoint[1]] {
                //且这个值小于原值 可直接返回false
                return false
            }
        }
        
        //右
        let nextPointRight = [enterPoint[0], enterPoint[1] + 1]
        let isOutRight = self.isOutSide(nextPointRight, matrix)
        
        if isOutRight {
            //越界
        }else{
            //没有越界
            if matrix[nextPointRight[0]][nextPointRight[1]] < matrix[enterPoint[0]][enterPoint[1]] {
                //且这个值小于原值 可直接返回false
                return false
            }
        }
        
        return true
    }
    
    
    //判断是否在界外
    func isOutSide(_ currentPoint:[Int], _ matrix: [[Int]]) -> Bool{
        let m = matrix.count-1
        let n = matrix[0].count-1
        if currentPoint[0] < 0 || currentPoint[0] > m ||
           currentPoint[1] < 0 || currentPoint[1] > n{
            return true
        }else{
            return false
        }
    }
    
    //
    func isEndPoint(_ enterPoint:[Int], _ matrix: [[Int]], _ flagArr:[[Bool]]) -> Bool{
        if enterPoint == [0,1] {
            print("1111")
        }
        //上
        let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
        let isOutUp = self.isOutSide(nextPointUp, matrix)
        
        if isOutUp {
            //越界
        }else{
            //没有越界
            if flagArr[nextPointUp[0]][nextPointUp[1]] == false {
                if matrix[nextPointUp[0]][nextPointUp[1]] > matrix[enterPoint[0]][enterPoint[1]] {
                    //且这个值大于原值 可直接返回false
                    return false
                }
            }
        }
        
        //左
        let nextLeft = [enterPoint[0], enterPoint[1] - 1]
        let isOutLeft = self.isOutSide(nextLeft, matrix)
        
        if isOutLeft {
            //越界
        }else{
            //没有越界
            if flagArr[nextLeft[0]][nextLeft[1]] == false {
                if matrix[nextLeft[0]][nextLeft[1]] > matrix[enterPoint[0]][enterPoint[1]] {
                    //且这个值大于原值 可直接返回false
                    return false
                }
            }
        }
        
        //下
        let nextDown = [enterPoint[0] + 1, enterPoint[1]]
        let isOutDown = self.isOutSide(nextDown, matrix)
        
        if isOutDown {
            //越界
        }else{
            //没有越界
            if flagArr[nextDown[0]][nextDown[1]] == false {
                if matrix[nextDown[0]][nextDown[1]] > matrix[enterPoint[0]][enterPoint[1]] {
                    //且这个值大于原值 可直接返回false
                    return false
                }
            }
        }
        
        //右
        let nextRight = [enterPoint[0], enterPoint[1] + 1]
        let isOutRight = self.isOutSide(nextRight, matrix)
        
        if isOutRight {
            //越界
        }else{
            //没有越界
            if flagArr[nextRight[0]][nextRight[1]] == false {
                if matrix[nextRight[0]][nextRight[1]] > matrix[enterPoint[0]][enterPoint[1]] {
                    //且这个值大于原值 可直接返回false
                    return false
                }
            }
        }
        return true
    }
    
    //考虑动态规划解法
}
